package A一周刷爆LeetCode.A基础班.F二叉树;

import java.util.Stack;

/**
 * @author wei.zhao
 * @description: 用递归和非递归两种方式实现二叉树的先序、中序、后序遍历
 * @date 2022年02月16日 16:11
 */
public class Code01_PreInPosTraversal {

    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);

        System.out.println("==============递归方式==============");
        System.out.print("pre-order: ");
        preOrderRecur(head);
        System.out.println();
        System.out.print("in-order: ");
        inOrderRecur(head);
        System.out.println();
        System.out.print("pos-order: ");
        posOrderRecur(head);
        System.out.println();

        System.out.println("============非递归方式=============");
        preOrderUnRecur(head);
        inOrderUnRecur(head);
        posOrderUnRecur1(head);
    }

    //递归先序遍历
    private static void preOrderRecur(Node head) {
        if (null == head) {
            return;
        }
        System.out.print(head.value + " ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

    //递归中序遍历
    private static void inOrderRecur(Node head) {
        if (null == head) {
            return;
        }
        inOrderRecur(head.left);
        System.out.print(head.value + " ");
        inOrderRecur(head.right);
    }

    //递归后序遍历
    private static void posOrderRecur(Node head) {
        if (null == head) {
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.print(head.value + " ");
    }

    //非递归先序遍历
    private static void preOrderUnRecur(Node head) {
        System.out.print("pre-order: ");
        if (null == head) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.add(head);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.print(node.value + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        System.out.println();
    }

    //非递归中序遍历
    private static void inOrderUnRecur(Node head) {
        System.out.print("in-order: ");
        if (null == head) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                System.out.print(head.value + " ");
                head = head.right;
            }
        }
        System.out.println();
    }

    //非递归后续遍历，方式一
    private static void posOrderUnRecur1(Node head) {
        System.out.print("pos-order: ");
        if (head == null) {
            return;
        }
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack1.push(head);
        while (!stack1.isEmpty()) {
            Node pop = stack1.pop();
            stack2.push(pop);
            if (pop.left != null) {
                stack1.push(pop.left);
            }
            if (pop.right != null) {
                stack1.push(pop.right);
            }
        }
        while (!stack2.isEmpty()) {
            Node pop = stack2.pop();
            System.out.print(pop.value + " ");
        }
    }

}
